class DFGNode:
    def __init__(self, vertex, parent):
        self.vertex = vertex
        self.children = []
        self._id_list = []
        self.parent = parent

    @property
    def is_root(self):
        return self.parent is None

    @property
    def index(self):
        return self.vertex.id

    def __len__(self):
        return len(self.children)

    def __getitem__(self, index):
        return self.children[index]

    def get(self, index):
        for child in self.children:
            if child.vertex.id == index:
                return child

    def has_child(self, child):
        return child.id in self._id_list

    def add_child(self, child):
        self.children.append(child)
        self._id_list.append(child.vertex.id)

    def accept(self, visitor):
        if len(self) == 0:
            return visitor.visit(self)

        if visitor.enter(self):
            for child in self.children:
                if not child.accept(visitor):
                    break
        return visitor.exit(self)


class DFGVisitor:
    def __init__(self):
        pass

    def enter(self, node: DFGNode):
        return True

    def exit(self, node: DFGNode):
        return True

    def visit(self, node: DFGNode):
        return True


class DFGPrinter(DFGVisitor):
    def __init__(self):
        self.depth = 0

    def enter(self, node: DFGNode):
        print("  " * self.depth + "begin: " + str(node.vertex))
        self.depth += 1
        return True

    def exit(self, node: DFGNode):
        self.depth -= 1
        print("  " * self.depth + "end: " + str(node.vertex))
        return True

    def visit(self, node: DFGNode):
        print("  " * self.depth + str(node.vertex))
        return True


def build_dfg_graph(paths):
    root = DFGNode(None, None)
    for path in paths:
        cur = root
        for vertex in path:
            if cur.has_child(vertex):
                cur = cur.get(vertex.id)
            else:
                child = DFGNode(vertex, cur)
                cur.add_child(child)
                cur = child
    return root
